package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/add-two-polynomials-represented-as-linked-lists'>求两个多项式链表的和(Add Two Polynomials Represented as Linked Lists)</a>
 * <p>多项式链表是一种特殊形式的链表，每个节点表示多项式的一项。</p>
 * <p>
 * 每个节点有三个属性：
 *     <ul>
 *         <li>coefficient：该项的系数。项 9x4 的系数是 9 。</li>
 *         <li>power：该项的指数。项 9x4 的指数是 4 。</li>
 *         <li>next：指向下一个节点的指针（引用），如果当前节点为链表的最后一个节点则为 null 。</li>
 *     </ul>
 * </p>
 * <p>
 *     例如，多项式 5x^3 + 4x - 7 可以表示成如下图所示的多项式链表：
 *     <pre>
 *         coefficient :5   4   -7  null
 *         power       :3   1   0
 *     </pre>
 * </p>
 * <p>多项式链表必须是标准形式的，即多项式必须 严格 按指数 power 的递减顺序排列（即降幂排列）。另外，系数 coefficient 为 0 的项需要省略。</p>
 * <p>给定两个多项式链表的头节点 poly1 和 poly2，返回它们的和的头节点。</p>
 * <p>
 *     PolyNode 格式：输入/输出格式表示为 n 个节点的列表，其中每个节点表示为 [coefficient, power] 。例如，多项式 5x^3 + 4x - 7 表示为： [[5,3],[4,1],[-7,0]] 。
 * </p>
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：poly1 = [[1,1]], poly2 = [[1,0]]
 *      输出：[[1,1],[1,0]]
 *      解释：poly1 = x. poly2 = 1. 和为 x + 1.
 *
 *  示例 2：
 *      输入：poly1 = [[2,2],[4,1],[3,0]], poly2 = [[3,2],[-4,1],[-1,0]]
 *      输出：[[5,2],[2,0]]
 *      解释：poly1 = 2x^2 + 4x + 3. poly2 = 3x^2 - 4x - 1. 和为 5x^2 + 2. 注意，我们省略 "0x" 项。
 *
 *  示例 3：
 *      输入：poly1 = [[1,2]], poly2 = [[-1,2]]
 *      输出：[]
 *      解释：和为 0。我们返回空链表。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>0 <= n <= 10^4</li>
 *     <li>-10^9 <= PolyNode.coefficient <= 10^9</li>
 *     <li>PolyNode.coefficient != 0</li>
 *     <li>0 <= PolyNode.power <= 10^9</li>
 *     <li>PolyNode.power > PolyNode.next.power</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/5/14 14:33
 */
public class LC1634AddTwpPolynomialsRepresentedAsLinkedList_M {
    static class Solution {
        public PolyNode addPoly(PolyNode poly1, PolyNode poly2) {
            PolyNode dummyHead = new PolyNode();
            PolyNode currNode = dummyHead;
            while (poly1 != null && poly2 != null) {
                int power1 = poly1.power;
                int power2 = poly2.power;
                if (power1 > power2) {
                    currNode.next = poly1;
                    poly1 = poly1.next;
                    currNode = currNode.next;
                } else if (power1 < power2) {
                    currNode.next = poly2;
                    poly2 = poly2.next;
                    currNode = currNode.next;
                } else {
                    int coefficientSum = poly1.coefficient + poly2.coefficient;
                    if (coefficientSum != 0) {
                        //poly1.coefficient += poly2.coefficient;
                        //currNode.next = poly1;
                        currNode.next = new PolyNode(coefficientSum, power1);
                        currNode = currNode.next;
                    }
                    poly1 = poly1.next;
                    poly2 = poly2.next;

                }
            }
            currNode.next = poly1 != null ? poly1 : poly2;
            return dummyHead.next;
        }
    }

    static class PolyNode {
        int coefficient;
        int power;
        PolyNode next = null;

        PolyNode() {
        }

        PolyNode(int coefficient, int power) {
            this.coefficient = coefficient;
            this.power = power;
        }

        PolyNode(int coefficient, int power, PolyNode next) {
            this.coefficient = coefficient;
            this.power = power;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        PolyNode poly1 = new PolyNode(1, 1);
        PolyNode poly2 = new PolyNode(1, 0);
        PolyNode polyNode = solution.addPoly(poly1, poly2);
        System.out.println(polyNode);
    }
}
